package kyssion.leetcode.num101_150;

/**
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
 * <p>
 * 说明：
 * <p>
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * <p>
 * 示例 1:
 * <p>
 * 输入: [2,2,3,2]
 * 输出: 3
 * 示例 2:
 * <p>
 * 输入: [0,1,0,1,0,1,99]
 * 输出: 99
 */
public class code137_只出现一次的数字2 {
    public static void main(String[] args) {
        System.out.println(new code137_只出现一次的数字2().singleNumber(
                new int[]{
                        1, 1, 1, 2, 2, 2, 3, 3, 3, 4
                }
        ));
    }

    //玄学......
    // 00 0或3次
    // 01 1次
    // 10 2次
    // ab 的第k位 初始00
    // num第k位为1时出现1次，00->01， 出现第二次 01->10，出现第三次 10->00，3次后该位为0
    // num第k位为0时出现任意次，ab均为00
    public int singleNumber(int[] nums) {
        int a = 0;
        int b = 0;
        for(int num : nums) {
            b = (b ^ num) & ~a;
            a = (a ^ num) & ~b;
        }
        return b;
    }
}
